package java_0220.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断是否是完全二叉树
 * 层序遍历实现
 */
public class Num958_CompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        if(root==null){
            return true;
        }
        Boolean isSecondStep=false;
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(!isSecondStep){
                //此时在第一状态
                if(cur.left!=null&&cur.right!=null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else if(cur.left!=null){
                    //只有左树没有右树，切换状态
                    isSecondStep=true;
                    //同时将左孩子入队
                    queue.offer(cur.left);
                }else if(cur.right!=null){
                    return false;
                }else{
                    //碰到叶子节点
                    isSecondStep=true;
                }

            }else{
                //此时在第二状态
                //所有节点都得是叶子节点
                if(cur.left!=null||cur.right!=null){
                    return false;
                }
            }
        }
        return true;
    }
}
